package com.zj.sixtyDayChallenge.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @program: algorithm
 * @description: 二叉树的中序遍历
 * 94 binary-tree-inorder-traversal
 * //给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：root = [1,null,2,3]
 * //输出：[1,3,2]
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：root = []
 * //输出：[]
 * //
 * //
 * // 示例 3：
 * //
 * //
 * //输入：root = [1]
 * //输出：[1]
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 树中节点数目在范围 [0, 100] 内
 * // -100 <= Node.val <= 100
 * //
 * //
 * //
 * //
 * // 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
 * //
 * // Related Topics 栈 树 深度优先搜索 二叉树 👍 1691 👎 0
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class BinaryTreeInorderTraversal {
	public static void main(String[] args) {
		Solution solution = new BinaryTreeInorderTraversal().new Solution();
	}
	//leetcode submit region begin(Prohibit modification and deletion)

	public static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	class Solution {
		public List<Integer> inorderTraversal(TreeNode root) {

			if (root == null) {
				return new ArrayList<>();
			}
			ArrayList<Integer> list = new ArrayList<>();
			this.invoke(root, list);
			return list;
		}

		private void invoke(TreeNode root, ArrayList<Integer> list) {
			if (root.left != null) {
				this.invoke(root.left, list);
			}
			list.add(root.val);
			if (root.right != null) {
				this.invoke(root.right, list);
			}
		}

		private void dfs(TreeNode root, List<Integer> list) {
			if (root.left != null) {
				this.dfs(root, list);
			}
			list.add(root.val);
			if (root.right != null) {
				this.dfs(root, list);
			}
		}


		public List<Integer> mid(TreeNode root) {
			List<Integer> list = new ArrayList<>();
			if (root == null) {
				return list;
			}

			Stack<TreeNode> stack = new Stack<>();
			TreeNode cur = root;
			while (cur != null || !stack.isEmpty()) {
				while (cur != null) {
					stack.push(cur);
					cur = cur.left;
				}
				cur = stack.pop();
				list.add(cur.val);
				cur = cur.right;

			}

			return list;
		}


		public List<Integer> mid1(TreeNode root) {
			ArrayList<Integer> list = new ArrayList<>();

			if (root == null) {
				return list;
			}

			TreeNode cur = root;

			Stack<TreeNode> stack = new Stack<>();

			while (cur != null || !stack.isEmpty()) {
				while (cur != null) {
					stack.push(cur);
					cur = cur.left;
				}

				cur = stack.pop();
				list.add(cur.val);
				cur = cur.right;
			}

			return list;
		}

	}
//leetcode submit region end(Prohibit modification and deletion)

}